﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Algorithm.Easy_53_MaximumSubarraySum
{
    //动态规划解决 暂时不理解
    class MainProject
    {
        static void Main(string[] args)
        {
            int[] nums = new int[] { -2, 1, -3, 4, -1, 2, 1, -5, 4};
            Console.WriteLine(MaxSubArray1(nums));
            Console.ReadKey();
        }

        public static int MaxSubArray1(int[] nums)
        {
            List<int> numsList = nums.ToList();

            for (int i = 0; i < numsList.Count; i++)
            {
                if (i==0)
                    continue;
                if (numsList[i-1]>0)
                {
                    numsList[i] += numsList[i - 1];
                }
            }
            return numsList.Max();
        }

        //超出时间限制了(未完)
        public static int MaxSubArray(int[] nums)
        {
            if (nums.Length==1)
            {
                return nums[0];
            }
            int totalNum = -100;
            List<int> allNums = new List<int>();
            for (int i = 0; i < nums.Length; i++)
            {
                allNums.Clear();
                allNums.Add(nums[i]);
                for (int j = i+1; j < nums.Length; j++)
                {
                    allNums.Add(allNums[allNums.Count-1] + nums[j]);
                }
                int curMaxValue = GetMaxNum(allNums);
                if (totalNum< curMaxValue)
                {
                    totalNum = curMaxValue;
                }
            }
            return totalNum;
        }

        public static int GetMaxNum(List<int> vs)
        {
            int num = vs[0];
            for (int i = 1; i < vs.Count; i++)
            {
                if (num<vs[i])
                {
                    num = vs[i];
                }
            }
            return num;
        }

    }
}
